<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
  
    
    
<script>
    // 后端返回的就是列表项 select *
    // 前端要自行转数型结构
const list = [
  {
    id: 1001,
    parentId: 0,
    name: "AA",
  },
  {
    id: 1002,
    parentId: 1001,
    name: "BB",
  },
  {
    id: 1003,
    parentId: 1001,
    name: "CC",
  },
  {
    id: 1004,
    parentId: 1003,
    name: "DD",
  },
  {
    id: 1005,
    parentId: 1003,
    name: "EE",
  },
  {
    id: 1006,
    parentId: 1002,
    name: "FF",
  },
  {
    id: 1007,
    parentId: 1002,
    name: "GG",
  },
  {
    id: 1008,
    parentId: 1004,
    name: "HH",
  },
  {
    id: 1009,
    parentId: 1005,
    name: "II",
  },
];

// 暴力解法
function listToSimpleTree(data) {
    const res = []

    data.forEach(item => {
        const parent = data.find(node => node.id === item.parentId)
        if (parent) {
            parent.children = parent.children || []
            parent.children.push(item)
        } else {
            // 一级节点
            res.push(item)
        }
    });

    return res
}

console.time('listToSimpleTree')
console.log(listToSimpleTree(list));
console.timeEnd('listToSimpleTree')

// 优化时间复杂度，用空间换时间
// HashMap 记录每个节点的id和节点本身的映射关系
function listToTree(data) {
    // 空间换时间
    const obj = {}
    // 当数据项很庞大的时候，中国的地市级别的数据
    // O(1) 查找
    data.forEach(item =>{
        obj[item.id] = item
    })

    const res = []

    data.forEach(item => {
        const parent = obj[item.parentId]
        if (parent) {
            parent.children = parent.children || []
            parent.children.push(item)
        } else {
            res.push(item)
        }
    })

    return res
    // console.time
    // console.timeEnd
}
console.time('listToTree')
console.log(listToTree(list))
console.timeEnd('listToTree')

// 递归解法
function recursiveToTree(data) {
    function loop(key) {
        const arr = []
        data.forEach(item => {
            if (item.parentId === key) {
                item.children = loop(item.id)
                arr.push(item)
            }
        })
        return arr
    }
    return loop(0)
}
console.time('recursiveToTree')
console.log(recursiveToTree(list))
console.timeEnd('recursiveToTree')
</script>

</body>
</html>